package com.zp.self.module.level_4_算法练习.算法.动态规划;

/**
 * @author By ZengPeng
 */
public class 自定义_青蛙跳台阶II {
    //测试
    public static void main(String[] args) {

        System.out.println(new 自定义_青蛙跳台阶II().numWays(100));
    }

    /**
    题目：现在有一个 n 级的台阶 , 有一只青蛙，每次可以选择跳 1 至 n 级台阶 (但不能超过剩余台阶数量)。
          求该青蛙共有多少种跳法到达台阶顶部。

     示例 1：
     输入：n = 3
     输出：4
     解释：可以选的跳法有：[111,12,21,3] 总共4种

     提示： 1 <= n <= 30

    分析：【P 💜💜】 拿来糊弄数学不好的同学   hahahaha
       1.动态规划： dp[] 动态三步曲：
                 1. 定义数组元素的含义:dp[i] 每个高度为i的台阶 有多少种跳法
                 2. 找出数组元素之间的关系式--状态方程:dp[n] = sum( dp(n-1) + dp(n-2) + dp(n-3) +.....+ dp(1)+ dp(0))
                            n个台阶的跳法：
                                        第1次跳1个台阶，剩余n-1个台阶  有：dp(n-1) 种跳法
                                        第1次跳2个台阶，剩余n-2个台阶  有：dp(n-2) 种跳法
                                        ....
                                        第1次跳n-1个台阶，剩余1个台阶  有：dp(1) 种跳法
                                        第1次跳n个台阶，剩余0个台阶  有：dp(0) 种跳法  。 这里没有0个台阶，但是第一步跳n阶只有这一种跳法 ，所以dp[0]=1
                 3. 找出初始值: dp[0]=1 ，dp[1]=1
       2.数学：通过步骤1的分析: dp[n] = 2 * dp[n-1]  = 1<<(n-1)

    边界值 & 注意点：
       1.
     **/
    public int numWays(int n) {
        return 1<<(n-1);
    }
}
